package stack;

/**
 * 栈的链式存储结构
 * @author mengxin
 *
 * @param <T>
 */
public class LinkStack<T> implements Stack<T>{  
    
    /*将数据封装成结点*/  
    class Node  
    {  
        private Node pre;  
        private T data;  
    }  
      
    /*栈顶指针*/  
    private Node top;  
    private int size;//栈的大小  
    public LinkStack() {  
        this.top = null;  
        this.size = 0;  
    }  
    @Override  
    public boolean isEmpty() {  
        return size==0;  
    }  
  
    @Override  
    public void clear() {  
        top = null;  
        size = 0;  
          
    }  
  
    @Override  
    public T pop() {  
        if (top != null) {    
            T t = top.data;  
            // 改变栈顶指针    
            top = top.pre;    
            size--;    
            return t;    
        }    
        return null;   
    }  
  
    @Override  
    public boolean push(T data) {  
         Node node = new Node();    
         node.data = data;    
         node.pre = top;    
            // 改变栈顶指针    
        top = node;    
        size++;    
        return true;    
    }  
  
    @Override  
    public int length() {  
        return size;  
    }  
  
    @Override  
    public T peek() {  
        return top.data;  
    }  
     /*下表从1开始*/  
    @Override  
    public int search(T t) {  
        int count=0;  
        for(Node node= top;node.pre!=null;node = node.pre)  
        {  
            count++;  
            if(t.equals(node.data))  
                return size - count;  
        }  
        return 0;  
    }  
    @Override  
    public String toString() {  
         StringBuilder sb = new StringBuilder();    
            sb.append("LinkStack:"+length()+"\n[\n");    
            int count=0;  
            for (Node node = top;node!=null;node=node.pre) {    
                count++;  
                sb.append("   "+node.data.toString());    
                if (count != size + 1) {    
                    sb.append("\n");    
                }    
            }    
            sb.append("]");   
            System.out.println(count);  
            return sb.toString();    
    }   
    
    public static void main(String[] args) throws Exception{
    	Stack<Integer> stack = new LinkStack<Integer>();
		stack.push(1);
		stack.push(2);
		System.out.println("Stack length:"+stack.length());
		System.out.println(stack.toString());
		System.out.println(stack.search(2));
		System.out.println(stack.pop());
		System.out.println(stack.toString());
		stack.clear();
		System.out.println(stack.toString());
    }
} 
